Search results for "Earliest deadline first scheduling"
showing 6 items of 6 documents
Approximation algorithm for constrained coupled-tasks scheduling problem
2014
International audience; We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.
Looking for the best modes helps solving the MRCPSP/max
2013
The multi-mode resource-constrained project scheduling problem with minimum and maximum time lags MRCPSP/max is a very general project scheduling problem with multiple execution modes per activity, renewable and non-renewable resources and minimum and maximum time lags between activities. In this paper, we describe SA-EVA, an algorithm for the problem. SA-EVA first searches for the best mode for each activity, without considering renewable resources. In this phase a simulated annealing is applied. Once a mode vector has been chosen, the problem reduces to the RCPSP/max, which SA-EVA solves with EVA, an algorithm designed in Ballestin et al. [2009. An evolutionary algorithm for the resource-…
Optimal deadline assignment for periodic real-time tasks in dynamic priority systems
2006
Real-time systems are often designed using a set of periodic tasks. Task periods are usually set by the system requirements, but deadlines and computation times can be modified in order to improve system performance. Sensitivity analysis in real-time systems has focused on changes in task computation times using fixed priority analysis. Only a few studies deal with the modification of deadlines in dynamic priority scheduling. The aim of this work is to provide a sensitivity analysis for task deadlines in the context of dynamic-priority, pre-emptive, uniprocessor scheduling. In this paper, we present a deadline minimisation method that achieves the maximum reduction. As undertaken in other s…
Dynamic scheduling of periodic skippable tasks in an overloaded real-time system
2008
International audience; The need for supporting dynamic real-time environments where changes in workloads may occur requires a scheduling framework that explicitly addresses overload conditions, allows the system to achieve graceful degradation and supports a mechanism capable of determining the load to be shed from the system to handle the overload. In applications ranging from video reception to air-craft control, tasks enter periodically and have response time constraints, but missing a deadline is acceptable, provided most deadlines are met. Such tasks are said to be occasionally skippable and have an assigned skip parameter. We look at the problem of uniprocessor scheduling of skippabl…
Deadline-based QoS Algorithms for High-performance Networks
2007
Quality of service (QoS) is becoming an attractive feature for high-performance networks and parallel machines because it could allow a more efficient use of resources. Deadline-based algorithms can provide powerful QoS provision. However, the cost associated with keeping ordered lists of packets makes them impractical for high-performance networks. In this paper, we explore how to adapt efficiently the earliest deadline first family of algorithms to the high-speed networks environments. The results show excellent performance using just two virtual channels, FIFO queues, and a cost feasible with today's technology.
Software-Based EDF Message Scheduling on CAN Networks
2006
In this paper, a CAN-based communication system has been used to transmit data between different kinds of sensors and the drive control of an electrical vehicle. Software-based earliest deadline first (EDF) scheduling has been applied to order the data, making possible that more relevant measures meet with their delivery time and, discarding, if necessary, less relevant ones are discarded. The messages use their time-to-deadline as their priority level. With this mechanism, alongside with the discard of data that has lost its deadline, is it possible to deal with saturated that would require a bus utilization well above 100%.